home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 420_02 / hexmaze.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-14  |  47.7 KB  |  1,236 lines
  1. #include <stdlib.h>
  2. #include <iostream.h>
  3. #include "oracle.h"
  4. #include "cell.h"
  5. #include "titillat.h"
  6. #include "hexmaze.h"
  7.  
  8. #define TRUE -1
  9. #define FALSE 0
  10.  
  11. typedef cell *cell_ptr;
  12. typedef char *char_ptr;
  13.  
  14. maze::maze(int row_count,int column_count,int thickness_of_wall,char *seed)
  15. //      Contruct a maze having "row_count" rows and "column_count" columns of
  16. // rooms.  The walls should be "thickness_of_wall" (bricks) thick.  A different
  17. // (8 character of less) "seed" generally yields a different maze.
  18.   {
  19.     struct
  20.       {
  21.          int row_num;
  22.          int column_num;
  23.       }  delta [2] [6];
  24.     int  mud_filled_room_found;
  25.     struct
  26.       {
  27.          int row_num;
  28.          int column_num;
  29.       }  next;
  30.     char wall [720] [6];
  31.     char wall_to_check;
  32.     char wall_num;
  33.     char way_out;
  34.     int  x1;
  35.     int  x2;
  36.     int  y1;
  37.     int  y2;
  38.  
  39.     wall_thickness=thickness_of_wall;
  40.     num_rows=row_count;
  41.     num_y_dots=wall_thickness*(4*num_rows+1);
  42.     y_dot_max=num_y_dots-1;
  43.     num_columns=column_count;
  44.     max_x=8*(num_columns/2)+6;
  45.     num_x_dots=wall_thickness*(max_x+1);
  46.     x_dot_max=num_x_dots-1;
  47.     // Allocate a two dimensional array of rooms.
  48.     if (memory_allocated=((room=new cell_ptr[num_rows]) != NULL))
  49.       {
  50.               int row_num=0;
  51.         while (memory_allocated && (row_num < num_rows))
  52.           if (memory_allocated=((room[row_num]=new cell [num_columns]) != NULL))
  53.             row_num++;
  54.         if (! memory_allocated)
  55.           {
  56.             while (row_num)
  57.               delete [] room[--row_num];
  58.             delete [] room;
  59.             cerr << "Fatal error:  cannot allocate maze.\n";
  60.           }
  61.       }
  62.     if (memory_allocated)
  63.       {
  64.          // Allocate a two dimensional array for plotting the maze in
  65.          // terms of "bricks" where a wall is "wall_thickness" bricks
  66.          // thick.
  67.          if (memory_allocated=((page=new char_ptr [num_y_dots]) != NULL))
  68.            {
  69.              int y_dot_num=0;
  70.              while (memory_allocated && (y_dot_num < num_y_dots))
  71.                if (memory_allocated=((page[y_dot_num]=new char [num_x_dots])
  72.                 != NULL))
  73.                  y_dot_num++;
  74.              if (! memory_allocated)
  75.                {
  76.                   while (y_dot_num)
  77.                     delete [] page[--y_dot_num];
  78.                   delete [] page;
  79.                   for (int row_num=num_rows-1; row_num >= 0; row_num--)
  80.                     delete [] room[row_num];
  81.                   delete [] room;
  82.                   cerr << "Fatal error:  cannot allocate maze.\n";
  83.                }
  84.            }
  85.          else
  86.            {
  87.               for (int row_num=num_rows-1; row_num >= 0; row_num--)
  88.                 delete [] room[row_num];
  89.               delete [] room;
  90.               cerr << "Fatal error:  cannot allocate maze.\n";
  91.            }
  92.       }
  93.     if (memory_allocated)
  94.       {
  95.          // Set up the directions by which a room can be exited.
  96.          // Directions for even columns.
  97.          delta[0][0].row_num=-1;    // north
  98.          delta[0][0].column_num=0;
  99.          delta[0][1].row_num=-1;    // northwest
  100.          delta[0][1].column_num=-1;
  101.          delta[0][2].row_num=0;     // southwest
  102.          delta[0][2].column_num=-1;
  103.          delta[0][3].row_num=1;     // south
  104.          delta[0][3].column_num=0;
  105.          delta[0][4].row_num=0;     // southeast
  106.          delta[0][4].column_num=1;
  107.          delta[0][5].row_num=-1;    // northeast
  108.          delta[0][5].column_num=1;
  109.          // Directions for odd columns.
  110.          delta[1][0].row_num=-1;    // north
  111.          delta[1][0].column_num=0;
  112.          delta[1][1].row_num=0;     // northwest
  113.          delta[1][1].column_num=-1;
  114.          delta[1][2].row_num=1;     // southwest
  115.          delta[1][2].column_num=-1;
  116.          delta[1][3].row_num=1;     // south
  117.          delta[1][3].column_num=0;
  118.          delta[1][4].row_num=1;     // southeast
  119.          delta[1][4].column_num=1;
  120.          delta[1][5].row_num=0;     // northeast
  121.          delta[1][5].column_num=1;
  122.          // Set up the 6! orders in which the wall of a room can be accessed.
  123.          int order_num=0;
  124.          for (int wall_num_1=0; wall_num_1 < 6; wall_num_1++)
  125.            for (int wall_num_2=0; wall_num_2 < 6; wall_num_2++)
  126.              if (wall_num_2 != wall_num_1)
  127.                for (int wall_num_3=0; wall_num_3 < 6; wall_num_3++)
  128.                  if ((wall_num_3 != wall_num_2)
  129.                  &&  (wall_num_3 != wall_num_1))
  130.                    for (int wall_num_4=0; wall_num_4 < 6; wall_num_4++)
  131.                      if ((wall_num_4 != wall_num_3)
  132.                      &&  (wall_num_4 != wall_num_2)
  133.                      &&  (wall_num_4 != wall_num_1))
  134.                        for (int wall_num_5=0; wall_num_5 < 6; wall_num_5++)
  135.                          if ((wall_num_5 != wall_num_4)
  136.                          &&  (wall_num_5 != wall_num_3)
  137.                          &&  (wall_num_5 != wall_num_2)
  138.                          &&  (wall_num_5 != wall_num_1))
  139.                            for (int wall_num_6=0; wall_num_6 < 6; wall_num_6++)
  140.                              if ((wall_num_6 != wall_num_5)
  141.                              &&  (wall_num_6 != wall_num_4)
  142.                              &&  (wall_num_6 != wall_num_3)
  143.                              &&  (wall_num_6 != wall_num_2)
  144.                              &&  (wall_num_6 != wall_num_1))
  145.                                {
  146.                                  wall[order_num][wall_num_6]='\0';
  147.                                  wall[order_num][wall_num_5]='\1';
  148.                                  wall[order_num][wall_num_4]='\2';
  149.                                  wall[order_num][wall_num_3]='\3';
  150.                                  wall[order_num][wall_num_2]='\4';
  151.                                  wall[order_num][wall_num_1]='\5';
  152.                                  order_num++;
  153.                                }
  154.          titillator_ptr=new titillator;
  155.          order_selector=new oracle(&seed[0],order_num);
  156.          row_selector=new oracle(&seed[0],num_rows);
  157.          column_selector=new oracle(&seed[0],num_columns);
  158.          int finished=FALSE;
  159.          // Generate mazes until you have one that is hard to solve.
  160.          do
  161.            {
  162.               // Pick a starting room.
  163.               first.column_num=column_selector->random_number();
  164.               if ((first.column_num)%2)
  165.                 do
  166.                   {
  167.                     first.row_num=row_selector->random_number();
  168.                   }
  169.                 while (first.row_num == (num_rows-1));
  170.               else
  171.                 first.row_num=row_selector->random_number();
  172.               current.row_num=first.row_num;
  173.               current.column_num=first.column_num;
  174.               // Excavate the starting room.
  175.               room[current.row_num][current.column_num].mark_floor(' ');
  176.               // Pick the order in which the walls of the starting room will be
  177.               // considered.
  178.               room[current.row_num][current.column_num].set_order(
  179.                order_selector->random_number());
  180.               titillator_ptr->titillate();
  181.               // Excavate rooms until there are no more to excavate.
  182.               do
  183.                 {
  184.                    mud_filled_room_found=FALSE;
  185.                    // Find an adjacent room (not yet considered) that needs
  186.                    // excavating.
  187.                    do
  188.                      {
  189.                         wall_num=room[current.row_num][
  190.                          current.column_num].next_wall_num();
  191.                         if (wall_num < '\6')
  192.                           {
  193.                              wall_to_check=wall[room[current.row_num][
  194.                               current.column_num].order_to_check()][wall_num];
  195.                              if (room[current.row_num][
  196.                               current.column_num].wall_up(wall_to_check))
  197.                                {
  198.                                   next.column_num=current.column_num
  199.                                    +delta[(current.column_num)%2]
  200.                                    [wall_to_check].column_num;
  201.                                   if ((next.column_num >= 0)
  202.                                   &&  (next.column_num < num_columns))
  203.                                     {
  204.                                       next.row_num=current.row_num
  205.                                        +delta[(current.column_num)%2]
  206.                                        [wall_to_check].row_num;
  207.                                       if ((next.row_num >= 0)
  208.                                       &&  ((((next.column_num)%2 == 1)
  209.                                          && (next.row_num < (num_rows-1)))
  210.                                        ||  (((next.column_num)%2 == 0)
  211.                                          && (next.row_num < num_rows))))
  212.                                         {
  213.                                            if (room[next.row_num][
  214.                                             next.column_num].mark()
  215.                                             == 'M')
  216.                                              mud_filled_room_found=TRUE;
  217.                                         }
  218.                                     }
  219.                                }
  220.                           }
  221.                      }
  222.                    while ((wall_num < '\6')
  223.                    &&     (! mud_filled_room_found));
  224.                    if (mud_filled_room_found)
  225.                    // an adjacent room needs excavating
  226.                      {
  227.                         // Exit the current room, knocking down a wall.
  228.                         room[current.row_num][
  229.                          current.column_num].knock_down_wall(wall_to_check);
  230.                         way_out=char(((int) wall_to_check+3)%6);
  231.                         // Enter the adjacent room, knocking down a wall.
  232.                         room[next.row_num][next.column_num].knock_down_wall(
  233.                          way_out);
  234.                         // Record how to return to the previous room.
  235.                         room[next.row_num][next.column_num].set_way_out(
  236.                          way_out);
  237.                         current.row_num=next.row_num;
  238.                         current.column_num=next.column_num;
  239.                         // Excavate the room.
  240.                         room[current.row_num][current.column_num].mark_floor(
  241.                          ' ');
  242.                         // Select the order in which the walls of the room will
  243.                         // be considered.
  244.                         room[current.row_num][current.column_num].set_order(
  245.                          order_selector->random_number());
  246.                      }
  247.                    else
  248.                    // no adjacent room needs excavating
  249.                      {
  250.                         if ((first.row_num != current.row_num)
  251.                         ||  (first.column_num != current.column_num))
  252.                           {
  253.                              // Go back to the room from which you entered
  254.                              // the current room.
  255.                              next.row_num=current.row_num+delta[
  256.                               (current.column_num)%2]
  257.                               [room[current.row_num]
  258.                               [current.column_num].way_back()].row_num;
  259.                              next.column_num=current.column_num+delta[
  260.                               (current.column_num)%2]
  261.                               [room[current.row_num]
  262.                               [current.column_num].way_back()].column_num;
  263.                              current.row_num=next.row_num;
  264.                              current.column_num=next.column_num;
  265.                           }
  266.                      }
  267.                 }
  268.               while ((first.row_num != current.row_num)
  269.               ||     (first.column_num != current.column_num)
  270.               ||     (wall_num < '\6'));
  271.               if (maze_okay()) // Maze is hard to solve.
  272.                 finished=TRUE;
  273.               else             // Prepare to try another maze.
  274.                 for (int row_num=0; row_num < num_rows; row_num++)
  275.                   for (int column_num=0; column_num < num_columns; column_num++)
  276.                     room[row_num][column_num].reinitialize();
  277.            }
  278.          while (! finished);
  279.          // Knock down walls blocking the entrance and exit to the maze.
  280.          room[0][0].knock_down_wall(0);
  281.          room[num_rows-1][num_columns-1].knock_down_wall(3);
  282.  
  283.          delete column_selector;
  284.          delete row_selector;
  285.          delete order_selector;
  286.  
  287.          // Generate a 2D plot of the maze.  Each element of "page" corresponds
  288.          // to a possible position of a brick composing the maze.  An element
  289.          // has value 'W' if a brick is present and value ' ' otherwise.  Each
  290.          // wall is "wall_thickness" bricks thick.
  291.          for (y1=0; y1 < num_y_dots; y1++)
  292.            for (x1=0; x1 < num_x_dots; x1++)
  293.              page[y1][x1]=' ';
  294.          for (int row_num=0; row_num < num_rows; row_num++)
  295.            {
  296.              int half_column_num=0;
  297.              for (int column_num=0; column_num < num_columns; column_num+=2)
  298.                {
  299.                  if (room[row_num][column_num].wall_up('\0'))
  300.                    {
  301.                       x1=8*half_column_num+2;
  302.                       y1=4*row_num;
  303.                       x2=x1+2;
  304.                       y2=y1;
  305.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  306.                        wall_thickness*x2,wall_thickness*y2);
  307.                       //    ***
  308.                       //   O   O
  309.                       //  O     OOO
  310.                       //   O   O
  311.                       //    OOO
  312.                    }
  313.                  half_column_num++;
  314.                }
  315.              half_column_num=0;
  316.              for (column_num=0; column_num < num_columns; column_num+=2)
  317.                {
  318.                  if (room[row_num][column_num].wall_up('\1'))
  319.                    {
  320.                       x1=8*half_column_num;
  321.                       y1=4*row_num+2;
  322.                       x2=x1+2;
  323.                       y2=y1-2;
  324.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  325.                        wall_thickness*x2,wall_thickness*y2);
  326.                       //    *OO
  327.                       //   *   O
  328.                       //  *     OOO
  329.                       //   O   O
  330.                       //    OOO
  331.                    }
  332.                  if (room[row_num][column_num].wall_up('\5'))
  333.                    {
  334.                       x1=8*half_column_num+4;
  335.                       y1=4*row_num;
  336.                       x2=x1+2;
  337.                       y2=y1+2;
  338.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  339.                        wall_thickness*x2,wall_thickness*y2);
  340.                       //    OO*
  341.                       //   O   *
  342.                       //  O     *OO
  343.                       //   O   O
  344.                       //    OOO
  345.                    }
  346.                  half_column_num++;
  347.                }
  348.              half_column_num=0;
  349.              for (column_num=0; column_num < (num_columns-1); column_num+=2)
  350.                {
  351.                   if (row_num != (num_rows-1))
  352.                     {
  353.                       if (room[row_num][column_num+1].wall_up('\0'))
  354.                         {
  355.                            x1=8*half_column_num+6;
  356.                            y1=4*row_num+2;
  357.                            x2=x1+2;
  358.                            y2=y1;
  359.                            draw_line_on_page(wall_thickness*x1,
  360.                             wall_thickness*y1,wall_thickness*x2,
  361.                             wall_thickness*y2);
  362.                            //    OOO
  363.                            //   O   O
  364.                            //  O     ***
  365.                            //   O   O
  366.                            //    OOO
  367.                         }
  368.                     }
  369.                  half_column_num++;
  370.                }
  371.              half_column_num=0;
  372.              for (column_num=0; column_num < num_columns; column_num+=2)
  373.                {
  374.                  if (room[row_num][column_num].wall_up('\2'))
  375.                    {
  376.                       x1=8*half_column_num;
  377.                       y1=4*row_num+2;
  378.                       x2=x1+2;
  379.                       y2=y1+2;
  380.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  381.                        wall_thickness*x2,wall_thickness*y2);
  382.                       //    OOO
  383.                       //   O   O
  384.                       //  *     OOO
  385.                       //   *   O
  386.                       //    *OO
  387.                    }
  388.                  if (room[row_num][column_num].wall_up('\4'))
  389.                    {
  390.                       x1=8*half_column_num+4;
  391.                       y1=4*row_num+4;
  392.                       x2=x1+2;
  393.                       y2=y1-2;
  394.                       draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  395.                        wall_thickness*x2,wall_thickness*y2);
  396.                       //    OOO
  397.                       //   O   O
  398.                       //  O     *OO
  399.                       //   O   *
  400.                       //    OO*
  401.                    }
  402.                  half_column_num++;
  403.                }
  404.            }
  405.          int half_column_num=0;
  406.          for (int column_num=0; column_num < num_columns; column_num+=2)
  407.            {
  408.               if (room[num_rows-1][column_num].wall_up('\3'))
  409.                 {
  410.                    x1=8*half_column_num+2;
  411.                    y1=4*(num_rows-1)+4;
  412.                    x2=x1+2;
  413.                    y2=y1;
  414.                    draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  415.                     wall_thickness*x2,wall_thickness*y2);
  416.                    //    OOO
  417.                    //   O   O
  418.                    //  O     OOO
  419.                    //   O   O
  420.                    //    ***
  421.                 }
  422.               if (column_num+1 < num_columns)
  423.                 {
  424.                    if (room[num_rows-2][column_num+1].wall_up('\3'))
  425.                      {
  426.                         x1=8*half_column_num+6;
  427.                         y1=4*(num_rows-1)+2;
  428.                         x2=x1+2;
  429.                         y2=y1;
  430.                         draw_line_on_page(wall_thickness*x1,wall_thickness*y1,
  431.                          wall_thickness*x2,wall_thickness*y2);
  432.                         //    OOO
  433.                         //   O   O
  434.                         //  O     ***
  435.                         //   O   O
  436.                         //    OOO
  437.                      }
  438.                 }
  439.              half_column_num++;
  440.            }
  441.          delete titillator_ptr;
  442.       }
  443.   }
  444.  
  445. maze::~maze()
  446.   {
  447.     if (memory_allocated)
  448.       {
  449.         // Free dynamically allocated memory.
  450.         for (int y_dot_num=num_y_dots-1; y_dot_num >= 0; y_dot_num--)
  451.           delete [] page[y_dot_num];
  452.         delete [] page;
  453.         for (int row_num=num_rows-1; row_num >= 0; row_num--)
  454.           delete [] room[row_num];
  455.         delete [] room;
  456.       }
  457.   }
  458.  
  459. void maze::draw_line_on_page(
  460.   int  x1,
  461.   int  y1,
  462.   int  x2,
  463.   int  y2)
  464. //      Draw wall (of bricks) on "page".
  465.     {
  466.       int error;
  467.       int error_prime_x;
  468.       int error_prime_y;
  469.       int permissible_delta_x;
  470.       int permissible_delta_y;
  471.       int x;
  472.       int x_diff;
  473.       int y;
  474.       int y_diff;
  475.  
  476.       error=0;
  477.       if (x2 >= x1)
  478.         permissible_delta_x=1;
  479.       else
  480.         permissible_delta_x=-1;
  481.       if (y2 >= y1)
  482.         permissible_delta_y=1;
  483.       else
  484.         permissible_delta_y=-1;
  485.       x=x1;
  486.       y=y1;
  487.       x_diff=x2-x1;
  488.       y_diff=y2-y1;
  489.       set_point_on_page(x,y);
  490.       while ((x != x2) || (y != y2))
  491.         {
  492.           error_prime_x=error+permissible_delta_x*y_diff;
  493.           error_prime_y=error-permissible_delta_y*x_diff;
  494.           if (abs(error_prime_x) <= abs(error_prime_y))
  495.             {
  496.               x+=permissible_delta_x;
  497.               error=error_prime_x;
  498.             }
  499.           else
  500.             {
  501.               y+=permissible_delta_y;
  502.               error=error_prime_y;
  503.             }
  504.           set_point_on_page(x,y);
  505.         }
  506.       return;
  507.     }
  508.  
  509. int maze::maze_okay()
  510.   {
  511.     int  adjacency;
  512.     struct
  513.       {
  514.          int row_num;
  515.          int column_num;
  516.       }  delta [2] [6];
  517.     struct
  518.       {
  519.          int row_num;
  520.          int column_num;
  521.       }  next;
  522.     int  num_rooms_in_maze;
  523.     int  num_rooms_in_solution;
  524.     int  passage_found;
  525.     struct
  526.       {
  527.          int row_num;
  528.          int column_num;
  529.       }  previous;
  530.     int  result;
  531.     struct
  532.       {
  533.          int row_num;
  534.          int column_num;
  535.       }  saved;
  536.     char wall_to_check;
  537.     char way_out;
  538.  
  539.     // Set up the directions by which a room can be exited.
  540.     // Even columns.
  541.     delta[0][0].row_num=-1;    // north
  542.     delta[0][0].column_num=0;
  543.     delta[0][1].row_num=-1;    // northwest
  544.     delta[0][1].column_num=-1;
  545.     delta[0][2].row_num=0;     // southwest
  546.     delta[0][2].column_num=-1;
  547.     delta[0][3].row_num=1;     // south
  548.     delta[0][3].column_num=0;
  549.     delta[0][4].row_num=0;     // southeast
  550.     delta[0][4].column_num=1;
  551.     delta[0][5].row_num=-1;    // northeast
  552.     delta[0][5].column_num=1;
  553.     // Odd columns.
  554.     delta[1][0].row_num=-1;    // north
  555.     delta[1][0].column_num=0;
  556.     delta[1][1].row_num=0;     // northwest
  557.     delta[1][1].column_num=-1;
  558.     delta[1][2].row_num=1;     // southwest
  559.     delta[1][2].column_num=-1;
  560.     delta[1][3].row_num=1;     // south
  561.     delta[1][3].column_num=0;
  562.     delta[1][4].row_num=1;     // southeast
  563.     delta[1][4].column_num=1;
  564.     delta[1][5].row_num=0;     // northeast
  565.     delta[1][5].column_num=1;
  566.     // Solve the maze.
  567.  
  568.     // Start at the entrance.
  569.     current.row_num=0;
  570.     current.column_num=0;
  571.     // Mark the room as part of the solution.
  572.     room[current.row_num][current.column_num].mark_floor('S');
  573.     num_rooms_in_solution=1;
  574.     // Prepare to consider all the walls of the room.
  575.     room[current.row_num][current.column_num].zero_wall_to_check();
  576.     // Try rooms until you get to the exit.
  577.     do
  578.       {
  579.         // Find a passage (not yet considered) out of the current room leading
  580.         // to a room not part of the proposed solution.
  581.         passage_found=FALSE;
  582.         do
  583.           {
  584.             wall_to_check
  585.              =room[current.row_num][current.column_num].next_wall_num();
  586.             if (wall_to_check < '\6')
  587.               {
  588.                  if (! (room[current.row_num][
  589.                   current.column_num].wall_up(wall_to_check)))
  590.                    {
  591.                       next.column_num=current.column_num
  592.                        +delta[(current.column_num)%2]
  593.                        [wall_to_check].column_num;
  594.                       if ((next.column_num >= 0)
  595.                       &&  (next.column_num < num_columns))
  596.                         {
  597.                           next.row_num=current.row_num
  598.                            +delta[(current.column_num)%2]
  599.                            [wall_to_check].row_num;
  600.                           if ((next.row_num >= 0)
  601.                           &&  ((((next.column_num)%2 == 1)
  602.                              && (next.row_num < (num_rows-1)))
  603.                            ||  (((next.column_num)%2 == 0)
  604.                              && (next.row_num < num_rows))))
  605.                             {
  606.                                if (room[next.row_num][
  607.                                 next.column_num].mark()
  608.                                 == ' ')
  609.                                  passage_found=TRUE;
  610.                             }
  611.                         }
  612.                    }
  613.               }
  614.           }
  615.         while ((! passage_found) && (wall_to_check < '\6'));
  616.         if (passage_found)
  617.         // passage to room not currently part of proposed solution found
  618.           {
  619.             // Enter the room.
  620.             current.row_num=next.row_num;
  621.             current.column_num=next.column_num;
  622.             // Record the way back to the previous room.
  623.             way_out=char(((int) wall_to_check+3)%6);
  624.             room[current.row_num][current.column_num].set_way_out(way_out);
  625.             // Mark the room as part of the proposed solution.
  626.             room[current.row_num][current.column_num].mark_floor('S');
  627.             num_rooms_in_solution++;
  628.             // Prepare to consider all the walls of the room.
  629.             room[current.row_num][current.column_num].zero_wall_to_check();
  630.           }
  631.         else
  632.         // dead end
  633.           {
  634.             // Mark current room as not part of proposed solution.
  635.             room[current.row_num][current.column_num].mark_floor(' ');
  636.             num_rooms_in_solution--;
  637.             // Go back to the room from which this room was entered.
  638.             next.row_num=current.row_num+delta[(current.column_num)%2][
  639.              room[current.row_num][current.column_num].way_back()].row_num;
  640.             next.column_num=current.column_num+delta[(current.column_num)%2][
  641.              room[current.row_num][current.column_num].way_back()].column_num;
  642.             current.row_num=next.row_num;
  643.             current.column_num=next.column_num;
  644.           }
  645.       }
  646.     while((current.row_num != num_rows-1)
  647.     ||    (current.column_num != num_columns-1));
  648.  
  649.     // Now that the maze is solved, calculate the number of rooms in the
  650.     // solution (or outside the maze) that are adjacent to the rooms in
  651.     // the solution.
  652.     adjacency=0;
  653.     previous.row_num=-1;
  654.     previous.column_num=0;
  655.     current.row_num=0;
  656.     current.column_num=0;
  657.     do
  658.       {
  659.         for (wall_to_check='\0'; wall_to_check < '\6'; wall_to_check++)
  660.           if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  661.             {
  662.                next.column_num=current.column_num
  663.                 +delta[(current.column_num)%2]
  664.                 [wall_to_check].column_num;
  665.                if ((next.column_num >= 0)
  666.                &&  (next.column_num < num_columns))
  667.                  {
  668.                    next.row_num=current.row_num
  669.                     +delta[(current.column_num)%2]
  670.                     [wall_to_check].row_num;
  671.                    if ((next.row_num >= 0)
  672.                    &&  ((((next.column_num)%2 == 1)
  673.                       && (next.row_num < (num_rows-1)))
  674.                     ||  (((next.column_num)%2 == 0)
  675.                       && (next.row_num < num_rows))))
  676.                      {
  677.                         if (room[next.row_num][next.column_num].mark() == 'S')
  678.                           adjacency++;
  679.                      }
  680.                    else
  681.                      adjacency++;
  682.                  }
  683.                else
  684.                  adjacency++;
  685.             }
  686.           else
  687.             {
  688.                next.column_num=current.column_num
  689.                 +delta[(current.column_num)%2]
  690.                 [wall_to_check].column_num;
  691.                if ((next.column_num >= 0)
  692.                &&  (next.column_num < num_columns))
  693.                  {
  694.                    next.row_num=current.row_num
  695.                     +delta[(current.column_num)%2]
  696.                     [wall_to_check].row_num;
  697.                    if ((next.row_num >= 0)
  698.                    &&  ((((next.column_num)%2 == 1)
  699.                       && (next.row_num < (num_rows-1)))
  700.                     ||  (((next.column_num)%2 == 0)
  701.                       && (next.row_num < num_rows))))
  702.                      {
  703.                         if ((room[next.row_num][next.column_num].mark() == 'S')
  704.                         &&  ((previous.row_num != next.row_num)
  705.                           || (previous.column_num != next.column_num)))
  706.                           {
  707.                             saved.row_num=next.row_num;
  708.                             saved.column_num=next.column_num;
  709.                           }
  710.                      }
  711.                  }
  712.             }
  713.         previous.row_num=current.row_num;
  714.         previous.column_num=current.column_num;
  715.         current.row_num=saved.row_num;
  716.         current.column_num=saved.column_num;
  717.       }
  718.     while((current.row_num != num_rows-1)
  719.     ||    (current.column_num != num_columns-1));
  720.     for (wall_to_check='\0'; wall_to_check < '\6'; wall_to_check++)
  721.       if (room[current.row_num][current.column_num].wall_up(wall_to_check))
  722.         {
  723.            next.column_num=current.column_num
  724.             +delta[(current.column_num)%2]
  725.             [wall_to_check].column_num;
  726.            if ((next.column_num >= 0)
  727.            &&  (next.column_num < num_columns))
  728.              {
  729.                 next.row_num=current.row_num
  730.                  +delta[(current.column_num)%2]
  731.                  [wall_to_check].row_num;
  732.                 if ((next.row_num >= 0)
  733.                 &&  ((((next.column_num)%2 == 1)
  734.                    && (next.row_num < (num_rows-1)))
  735.                  ||  (((next.column_num)%2 == 0)
  736.                    && (next.row_num < num_rows))))
  737.                   {
  738.                      if (room[next.row_num][next.column_num].mark() == 'S')
  739.                        adjacency++;
  740.                   }
  741.                 else
  742.                   adjacency++;
  743.              }
  744.            else
  745.              adjacency++;
  746.         }
  747.     num_rooms_in_maze=num_rows*num_columns-(num_columns/2);
  748.  
  749.     // The maze is hard to solve (from the outside) if more than a third of its
  750.     // rooms are part of its solution and rooms not part of its solution tend to
  751.     // be next to rooms in its solution.
  752.     if ((3*num_rooms_in_solution >= num_rooms_in_maze)
  753.     &&  (5*adjacency <= 11*num_rooms_in_solution))
  754.       result=TRUE;
  755.     else
  756.       result=FALSE;
  757.     return result;
  758.   }
  759.  
  760. int maze::external_to_maze(double x,double y)
  761. //      Return TRUE if and only if a point (x,y) is external to the maze.
  762.   {
  763.     int result;
  764.     int x_out;
  765.     int x_next;
  766.     int y_out;
  767.     int y_next;
  768.  
  769.     result=FALSE;
  770.     y_out=(int) x;
  771.     if (y_out < 0)
  772.       result=TRUE;
  773.     else
  774.       if (y_out > y_dot_max)
  775.         result=TRUE;
  776.       else
  777.         {
  778.           x_out=(int) y;
  779.           if (x_out < 0)
  780.             result=TRUE;
  781.           else
  782.             if (x_out > x_dot_max)
  783.               result=TRUE;
  784.             else
  785.               // A point is external to the maze if you don't have to cross
  786.               // a wall, the entrance, or the exit to move from the point to
  787.               // outside the maze.
  788.               {
  789.                 if ((x_out/wall_thickness != 3)
  790.                 &&  (x_out/wall_thickness != max_x-3))
  791.                   {
  792.                     x_next=x_out;
  793.                     result=TRUE;
  794.                     while((result) && (x_next >= 0))
  795.                       {
  796.                         if (page[y_out][x_next] == ' ')
  797.                           x_next--;
  798.                         else
  799.                           result=FALSE;
  800.                       }
  801.                     if (! result)
  802.                       {
  803.                         x_next=x_out;
  804.                         result=TRUE;
  805.                         while((result) && (x_next <= x_dot_max))
  806.                           {
  807.                             if (page[y_out][x_next] == ' ')
  808.                               x_next++;
  809.                             else
  810.                               result=FALSE;
  811.                           }
  812.                       }
  813.                     if (! result)
  814.                       {
  815.                         y_next=y_out;
  816.                         result=TRUE;
  817.                         while((result) && (y_next >= 0))
  818.                           {
  819.                             if (page[y_next][x_out] == ' ')
  820.                               y_next--;
  821.                             else
  822.                               result=FALSE;
  823.                           }
  824.                       }
  825.                     if (! result)
  826.                       {
  827.                         y_next=y_out;
  828.                         result=TRUE;
  829.                         while((result) && (y_next <= y_dot_max))
  830.                           {
  831.                             if (page[y_next][x_out] == ' ')
  832.                               y_next++;
  833.                             else
  834.                               result=FALSE;
  835.                           }
  836.                       }
  837.                   }
  838.               }
  839.         }
  840.     return result;
  841.   }
  842.  
  843. double maze::f(double x,double y)
  844. //      Return 5.0*wall_thickness if a point (x,y) is on a wall, 0.0 otherwise.
  845.   {
  846.     int    x_out;
  847.     int    y_out;
  848.     double z;
  849.  
  850.     y_out=(int) x;
  851.     if (y_out < 0)
  852.       z=0.0;
  853.     else
  854.       if (y_out > y_dot_max)
  855.         z=0.0;
  856.       else
  857.         {
  858.           x_out=(int) y;
  859.           if (x_out < 0)
  860.             z=0.0;
  861.           else
  862.             if (x_out > x_dot_max)
  863.               z=0.0;
  864.             else
  865.               if (page[y_out][x_out] == 'W')
  866.                 z=1.0;
  867.               else
  868.                 z=0.0;
  869.         }
  870.     return z*double(5*wall_thickness);
  871.   }
  872.  
  873. int maze::part_of_solution(double x,double y)
  874. //      Return TRUE if and only if a point (x,y) is on a wall outlining the
  875. // solution to the maze.
  876.   {
  877.     int base_x;
  878.     int base_x_mod_8;
  879.     int base_y;
  880.     int base_y_mod_4;
  881.     int half_column_num;
  882.     int result;
  883.     int row_num;
  884.     int x_out;
  885.     int y_out;
  886.  
  887.     y_out=(int) x;
  888.     if (y_out < 0)
  889.       result=FALSE;
  890.     else
  891.       if (y_out > y_dot_max)
  892.         result=FALSE;
  893.       else
  894.         {
  895.           x_out=(int) y;
  896.           if (x_out < 0)
  897.             result=FALSE;
  898.           else
  899.             if (x_out > x_dot_max)
  900.               result=FALSE;
  901.             else
  902.               if (page[y_out][x_out] == 'W')
  903.                 {
  904.                   result=FALSE;
  905.                   base_x=x_out/wall_thickness;
  906.                   half_column_num=base_x/8;
  907.                   base_x_mod_8=base_x-8*half_column_num;
  908.                   base_y=y_out/wall_thickness;
  909.                   row_num=base_y/4;
  910.                   base_y_mod_4=base_y-4*row_num;
  911.                   switch (base_y_mod_4)
  912.                   //      000
  913.                   //     1   1
  914.                   //    2     22 
  915.                   //     3   3
  916.                   //      000
  917.                     {
  918.                       case 0:
  919.                         if (base_x_mod_8 < 3)
  920.                         //      *00
  921.                         //     1   1
  922.                         //    2     22
  923.                         //     3   3
  924.                         //      000
  925.                           {
  926.                             if (row_num < num_rows)
  927.                               {
  928.                                 if (room[row_num][2*half_column_num].mark()
  929.                                  == 'S')
  930.                                   result=TRUE;
  931.                               }
  932.                             if (! result)
  933.                               {
  934.                                 if (row_num > 0)
  935.                                   {
  936.                                     if (room[row_num-1]
  937.                                      [2*half_column_num].mark() == 'S')
  938.                                       result=TRUE;
  939.                                   }
  940.                               }
  941.                             if (! result)
  942.                               {
  943.                                 if (row_num > 0)
  944.                                   {
  945.                                     if (half_column_num > 0)
  946.                                       {
  947.                                         if (room[row_num-1]
  948.                                          [2*half_column_num-1].mark() == 'S')
  949.                                           result=TRUE;
  950.                                       }
  951.                                   }
  952.                               }
  953.                           }
  954.                         else
  955.                           if (base_x_mod_8 > 3)
  956.                           //      00*
  957.                           //     1   1
  958.                           //    2     22
  959.                           //     3   3
  960.                           //      000
  961.                             {
  962.                               if (row_num < num_rows)
  963.                                 {
  964.                                   if (room[row_num][2*half_column_num].mark()
  965.                                    == 'S')
  966.                                     result=TRUE;
  967.                                 }
  968.                               if (! result)
  969.                                 {
  970.                                   if (row_num > 0)
  971.                                     {
  972.                                       if (room[row_num-1]
  973.                                        [2*half_column_num].mark() == 'S')
  974.                                         result=TRUE;
  975.                                     }
  976.                                 }
  977.                               if (! result)
  978.                                 {
  979.                                   if (row_num > 0)
  980.                                     {
  981.                                       if (2*half_column_num+1 < num_columns)
  982.                                         {
  983.                                           if ((row_num-1) < (num_rows-1))
  984.                                             {
  985.                                               if (room[row_num-1]
  986.                                                [2*half_column_num+1].mark()
  987.                                                == 'S')
  988.                                                 result=TRUE;
  989.                                             }
  990.                                         }
  991.                                     }
  992.                                 }
  993.                             }
  994.                           else
  995.                           //      0*0
  996.                           //     1   1
  997.                           //    2     22
  998.                           //     3   3
  999.                           //      000
  1000.                             {
  1001.                               if (row_num < num_rows)
  1002.                                 {
  1003.                                   if (room[row_num][2*half_column_num].mark()
  1004.                                    == 'S')
  1005.                                     result=TRUE;
  1006.                                 }
  1007.                               if (! result)
  1008.                                 {
  1009.                                   if (row_num > 0)
  1010.                                     {
  1011.                                       if (room[row_num-1]
  1012.                                        [2*half_column_num].mark() == 'S')
  1013.                                         result=TRUE;
  1014.                                     }
  1015.                                 }
  1016.                             }
  1017.                         break;
  1018.                       case 1:
  1019.                         if (base_x_mod_8 < 3)
  1020.                         //      000
  1021.                         //     *   1
  1022.                         //    2     22
  1023.                         //     3   3
  1024.                         //      000
  1025.                           {
  1026.                             if (room[row_num][2*half_column_num].mark() == 'S')
  1027.                               result=TRUE;
  1028.                             if (! result)
  1029.                               {
  1030.                                 if (row_num > 0)
  1031.                                   {
  1032.                                     if (half_column_num > 0)
  1033.                                       {
  1034.                                         if (room[row_num-1]
  1035.                                          [2*half_column_num-1].mark() == 'S')
  1036.                                           result=TRUE;
  1037.                                       }
  1038.                                   }
  1039.                               }
  1040.                           }
  1041.                         else
  1042.                         //      000
  1043.                         //     1   *
  1044.                         //    2     22
  1045.                         //     3   3
  1046.                         //      000
  1047.                           {
  1048.                             if (room[row_num][2*half_column_num].mark() == 'S')
  1049.                               result=TRUE;
  1050.                             if (! result)
  1051.                               {
  1052.                                 if (row_num > 0)
  1053.                                   {
  1054.                                     if (2*half_column_num+1 < num_columns)
  1055.                                       {
  1056.                                         if (room[row_num-1]
  1057.                                          [2*half_column_num+1].mark() == 'S')
  1058.                                           result=TRUE;
  1059.                                       }
  1060.                                   }
  1061.                               }
  1062.                           }
  1063.                         break;
  1064.                       case 2:
  1065.                         if (base_x_mod_8 < 3)
  1066.                         //      000
  1067.                         //     1   1
  1068.                         //    *     22
  1069.                         //     3   3
  1070.                         //      000
  1071.                           {
  1072.                             if (room[row_num][2*half_column_num].mark() == 'S')
  1073.                               result=TRUE;
  1074.                             else
  1075.                               {
  1076.                                 if (half_column_num > 0)
  1077.                                   {
  1078.                                     if (row_num > 0)
  1079.                                       {
  1080.                                         if (room[row_num-1]
  1081.                                          [2*half_column_num-1].mark() == 'S')
  1082.                                           result=TRUE;
  1083.                                       }
  1084.                                     if (! result)
  1085.                                       {
  1086.                                         if (row_num < (num_rows-1))
  1087.                                           {
  1088.                                             if (room[row_num]
  1089.                                              [2*half_column_num-1].mark()
  1090.                                              == 'S')
  1091.                                               result=TRUE;
  1092.                                           }
  1093.                                       }
  1094.                                   }
  1095.                               }
  1096.                           }
  1097.                         else
  1098.                           if (base_x_mod_8 < 7) // case 6
  1099.                           //      000
  1100.                           //     1   1
  1101.                           //    2     *2
  1102.                           //     3   3
  1103.                           //      000
  1104.                             {
  1105.                               if (room[row_num][2*half_column_num].mark()
  1106.                                == 'S')
  1107.                                 result=TRUE;
  1108.                               if (! result)
  1109.                                 {
  1110.                                   if (row_num < num_rows-1)
  1111.                                     {
  1112.                                       if (2*half_column_num+1 < num_columns)
  1113.                                         {
  1114.                                           if (room[row_num]
  1115.                                            [2*half_column_num+1].mark() == 'S')
  1116.                                             result=TRUE;
  1117.                                         }
  1118.                                     }
  1119.                                 }
  1120.                               if (! result)
  1121.                                 {
  1122.                                   if (row_num > 0)
  1123.                                     {
  1124.                                       if (2*half_column_num+1 < num_columns)
  1125.                                         {
  1126.                                           if (room[row_num-1]
  1127.                                            [2*half_column_num+1].mark() == 'S')
  1128.                                             result=TRUE;
  1129.                                         }
  1130.                                     }
  1131.                                 }
  1132.                             }
  1133.                           else
  1134.                           //      000
  1135.                           //     1   1
  1136.                           //    2     2*
  1137.                           //     3   3
  1138.                           //      000
  1139.                             {
  1140.                               if (row_num < (num_rows-1))
  1141.                                 {
  1142.                                   if (room[row_num][2*half_column_num+1].mark()
  1143.                                    == 'S')
  1144.                                     result=TRUE;
  1145.                                 }
  1146.                               if (! result)
  1147.                                 {
  1148.                                   if (row_num > 0)
  1149.                                     {
  1150.                                       if (room[row_num-1]
  1151.                                        [2*half_column_num+1].mark() == 'S')
  1152.                                         result=TRUE;
  1153.                                     }
  1154.                                 }
  1155.                             }
  1156.                         break;
  1157.                       default:
  1158.                         if (base_x_mod_8 < 3)
  1159.                         //      000
  1160.                         //     1   1
  1161.                         //    2     22
  1162.                         //     *   3
  1163.                         //      000
  1164.                           {
  1165.                             if (room[row_num][2*half_column_num].mark()
  1166.                              == 'S')
  1167.                               result=TRUE;
  1168.                             else
  1169.                               {
  1170.                                 if (half_column_num > 0)
  1171.                                   {
  1172.                                     if (row_num < (num_rows-1))
  1173.                                       {
  1174.                                         if (room[row_num]
  1175.                                          [2*half_column_num-1].mark() == 'S')
  1176.                                           result=TRUE;
  1177.                                       }
  1178.                                   }
  1179.                               }
  1180.                           }
  1181.                         else
  1182.                         //      000
  1183.                         //     1   1
  1184.                         //    2     22
  1185.                         //     3   *
  1186.                         //      000
  1187.                           {
  1188.                             if (room[row_num][2*half_column_num].mark()
  1189.                              == 'S')
  1190.                               result=TRUE;
  1191.                             if (! result)
  1192.                               {
  1193.                                 if (row_num < (num_rows-1))
  1194.                                   {
  1195.                                     if (2*half_column_num+1 < num_columns)
  1196.                                       {
  1197.                                         if (room[row_num]
  1198.                                          [2*half_column_num+1].mark()
  1199.                                          == 'S')
  1200.                                           result=TRUE;
  1201.                                       }
  1202.                                   }
  1203.                               }
  1204.                           }
  1205.                         break;
  1206.                     }
  1207.                 }
  1208.               else
  1209.                 result=FALSE;
  1210.         }
  1211.     return result;
  1212.   }
  1213.  
  1214. void maze::set_point_on_page(
  1215.   int  x,
  1216.   int  y)
  1217. //      Place a section of wall on "page".  Each section is "wall_thickness"
  1218. // bricks long and "wall_thickness" bricks wide.
  1219.     {
  1220.       int x_offset;
  1221.       int x_out;
  1222.       int y_offset;
  1223.       int y_out;
  1224.  
  1225.       for (x_offset=0; x_offset < wall_thickness; x_offset++)
  1226.         {
  1227.           x_out=x+x_offset;
  1228.           for (y_offset=0; y_offset < wall_thickness; y_offset++)
  1229.             {
  1230.               y_out=y+y_offset;
  1231.               page[y_out][x_out]='W';
  1232.             }
  1233.         }
  1234.       return;
  1235.     }
  1236.